\chapter{基于神经网络的高阶图表征方法}\label{chap:embedding} 

本章首先分别介绍了如何基于GCN和GAT对图做节点级别的表征和图级别的表征，接着讨论了引入局部结构Graphlet的一种直观的启发，并且设计了一种引入局部结构Graphlet的一种方法。

\section{基于GCN对图做表征}

    \subsection{节点表征方法}

        对于GCN而言，输入的是一个图的邻接矩阵$A$和特征矩阵$X\in\mathbb{R}^{\mathcal{N}\times \mathcal{d}}$,输出的是学到的新的特征矩阵$X'\in\mathbb{R}^{\mathcal{N}\times \mathcal{d}'}$.

        这样一种模型天然就可以对图上的节点做图表征，然而，这种方法存在以下的不足之处:

        
        \begin{itemize}
            \item 对于训练时没有出现过的节点，在测试的时候无法得到它的表征
            \item 受限于GCN需要计算$\tilde{\mathcal{L}}_{sym}$，GCN难以分批次训练，这阻碍了GCN在比较大的图上的发展。
            \item 节点的新特征向量均是通过邻居节点的特征向量聚合而来，不能很好的考虑图中天然的结构特征
            \item GCN所用的重归一化的拉普拉斯矩阵$\tilde{\mathcal{L}}_{sym}$的特征值均在$[-1,1]$上，于是当GCN层数叠加的多了之后，不可避免的会出现一个图上的所有节点的信息趋同(不动点)现象，这导致GCN不能堆叠很多层，从而限制了GCN的表征能力。
        \end{itemize}
        
        \begin{figure}[!htbp]
            \centering
            \includegraphics[width=0.7\textwidth]{Img/NaiveGraphEmbedding.png}
            \caption{最简单的通过节点特征获得图特征的方法}
            \label{fig:naiveGraphEmbedding}
        \end{figure}
        后两个不足是相互联系的，如果GCN所叠的层数很少，它能考虑的范围就仅限于有限层数的邻居，它能考虑的结构就是不完全的，而当GCN叠的层数足够多到考虑全局信息的时候，又由于过平滑，使得全部的节点得到的表征趋同。


    \subsection{图表征方法}
        GCN不能直接对图做表征，只能对图上的节点分别做表征，这样的话，我们就可以考虑使用图上的节点所具有的特征来得到图的特征。

        一种最简单的方法如图\ref{fig:naiveGraphEmbedding}就是将所有的节点特征向量拼接起来/取平均/取最大，令这样得到的向量为图的表征，然而这样的做法不能很好的考虑不同节点之间的差异，并且也抹去了图上的结构信息。

        为了考虑到不同节点之间的结构特征，我们可以采用图\ref{fig:topkpoolingProcess}的方法，对图做池化，从而得到分层的特征，最后将其整合起来。

        
\section{基于GAT对图做表征}

        \subsection{节点表征方法}
            与GCN类似的，GAT天然的也适合直接对图上的节点做表征。与一般的GCN不同的是，GAT通过引入attetion机制，可以学到那些邻居节点更加重要，从而在表征出的向量中那些更重要的邻居会产生更大的影响。同时GAT也解决了GCN在训练时没见过的节点无法得到表征这一问题。 

            然而GAT仍然没有解决下面的问题:

            \begin{itemize}
                \item 不能分批次训练，当图较大时，训练效率低
                \item GAT相较于GCN具有更多的参数，并且也只考虑了一阶邻居，故而不能很好的整合图的结构信息，从而在层数较深时容易过拟合。
            \end{itemize}

        \subsection{图表征方法}
            同GCN类似的，我们也可以采用图\ref{fig:topkpoolingProcess}的方法，对图做池化，从而得到分层的特征，最后将其整合起来。


\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{Img/topkpoolingProcess.png}
    \caption{两种可能的基于pooling做图分类的方式,引自\citep{TopK}}
    \label{fig:topkpoolingProcess}
\end{figure}

\section{为什么要引入局部结构Graphlet？}
    上述提到的图神经网络模型对图做表征，均只考虑了节点附近的一阶邻居，而没有很好的考虑到图的结构，这在一定程度上没有将图中富含的结构特征利用起来。

    Graphlets是从一个大的图中诱导出来的一组非同构子图。而Graphlet Degree Vector则是表示图上某种结构特性的向量。


\section{如何引入局部结构Graphlet？}
    在做图分类的任务时，部分图是没有节点属性的，对于这样的图，我们可以为每一个节点安排一个其对应的GDV来充当它的节点属性。而还有部分图带有节点属性，对于这样的图，情况就比较难办了。本文中，我们直接将节点原本就具有的属性与其对应的GDV拼接起来作为它的新的节点属性,如图\ref{fig:gdvembedding}.

    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.2\textwidth]{Img/addGDV.eps}
        \caption{引入GDV}
        \label{fig:gdvembedding}
    \end{figure}

\section{算法分析与讨论}

    通过引入GDV来充当节点属性或是扩展节点属性，我们期待能通过这种方法，让图表征过程能够更多的关注图的拓扑结构，从而学到能更好考虑结构的图特征。 

    与通常的GNN相比，GDV也可以看作是一种初始化每个节点具有的embedding的方法，如果原本的数据集不具备节点属性，那么我们在通常的GNN中就要为每一个节点准备一个随机的初始化embedding，之后再通过对数据集的学习不断的迭代从而得到比较好的图表征。

    有了GDV之后我们就可以选取GDV作为初始化的节点embedding，从而避免随机初始化节点属性带来的不确定因素，使训练更加的稳定。


\section{本章小结}
    本章首先讨论了如何基于GCN对图分别做节点级别的表征和图级别的表征，接着分析GCN存在的不足，并又讨论了GAT如何弥补了GCN中存在的不足，介绍了如何基于GAT对图分别做节点级别的表征和图级别的表征，也分析了GAT仍然存在的不足之处。

    随后，本章又讨论了复杂结构中的一种局部结构——Grahlet，对引入其到图神经网络中对图分类可能带来的益处做了分析，并讨论了一种可能的引入方式。